package jm.algorithm.back_tracking;

/**
 * @Description 位运算优化 8 / 4 皇后问题
 * @date 2022/5/19 19:38
 */
public class QueensBit {
    public static void main(String[] args) {
        new QueensBit().place8Queens();
    }

    // 判断当前行中是否已经存在皇后
    // 使用八位二字节代表行：10000000：代表第0列有皇后
    byte cols;

    // 判断 左上角 到 右下角 是否有皇后 即 ↘ 方向
    // 使用 十六位 四字节
    short leftTop;

    // 判断 右上角 到 左下角 是否有皇后 即 ↙ 方向
    // 使用 十六位 四字节
    short rightTop;

    // 统计摆法
    int ways;

    /**
     * n 皇后问题
     */
    void place8Queens(){
        place(0);
        System.out.println(ways);
    }

    /**
     * 从第 row 行开始摆放皇后
     * @param row 行
     */
    void place(int row){
        // 如果上一行摆放成功了，即符合所有摆放条件，最后一行不需要调用。
        if (row == 8) {
            ways++;
            return;
        }
        for (int col = 0; col < 8; col++) {
            // 不能摆就返回
            int colV = 1 << col;
            int lv = 1 << (row - col + 7);
            int rv = 1 << (row + col);

            if ((cols & colV) != 0) continue;
            if ((leftTop & lv) != 0) continue;
            if ((rightTop & rv) != 0) continue;

            // 摆放皇后
            cols |= colV;
            leftTop |= lv;
            rightTop |= rv;

            // 在下一行摆放皇后
            place(row + 1);
            // 回溯
            // 如果将某行的所有可能都摆放完了，会返回到他的上行中，对这行重新摆放，就实现了回溯;

            // 回溯时需要重置
            cols &= ~colV;
            leftTop &= ~lv;
            rightTop &= ~rv;
        }
    }
}
